////////////////////////////////////////////////////////////////////////////////////////////////////
/// Copyright (c) 2009 - 2010 RacoonStudios
///
/// Permission is hereby granted, free of charge, to any person obtaining a copy of this
/// software and associated documentation files (the "Software"), to deal in the Software
/// without restriction, including without limitation the rights to use, copy, modify, merge,
/// publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons
/// to whom the Software is furnished to do so, subject to the following conditions:
///
/// The above copyright notice and this permission notice shall be included in all copies or
/// substantial portions of the Software.
///
/// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED,
/// INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR
/// PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE
/// FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR
/// OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
/// DEALINGS IN THE SOFTWARE.
////////////////////////////////////////////////////////////////////////////////////////////////////

#pragma once
#ifndef priorityarray_h__
#define priorityarray_h__

#include "core/types.h"

namespace Helper
{
	////////////////////////////////////////////////////////////////////////////////////////////////////
	/// \class	PriorityArray
	///
	/// \brief	The PriorityArray is a special Array. It has only a specified amount of 
	///			elements taking place in it. When we want to add a new element to the
	///			PriorityArray and haven't reached the maximum size everything is okay.
	///			But when there is no space left we have to deside which element to delete.
	///			Normally the Node with the smallest Priority will be dropped.
	///			Of course, the element with the smallest Priority will only be deleted if 
	///			the new Node has a greater Priority.
	///			For a faster search for the Node with the smallest Priority we also have
	///			a variable containing the index of the Node with the smallest Priority.
	///
	/// \author	khaos
	/// \date	12.12.2009
	////////////////////////////////////////////////////////////////////////////////////////////////////
	template<class T>
	class PriorityArray
	{
		public:

			////////////////////////////////////////////////////////////////////////////////////////////////////
			/// \fn	PriorityArray()
			///	
			/// \brief	Default constructor. 
			///
			///	\author	khaos
			/// \date	12.12.2009
			////////////////////////////////////////////////////////////////////////////////////////////////////
			PriorityArray();

			////////////////////////////////////////////////////////////////////////////////////////////////////
			/// \fn	PriorityArray(tSize size)
			///
			/// \brief	Constructor. 
			///
			/// \author	khaos
			/// \date	12.12.2009
			///
			/// \param	[in]	size	The size the PriorityArray should have.
			////////////////////////////////////////////////////////////////////////////////////////////////////
			PriorityArray(tSize size);

			////////////////////////////////////////////////////////////////////////////////////////////////////
			/// \fn	PriorityArray(const PriorityArray<T> & rhs)
			///
			/// \brief	Constructor. 
			///
			/// \author	khaos
			/// \date	12.12.2009
			///
			/// \param	[in]	rhs	The right hand side object. 
			////////////////////////////////////////////////////////////////////////////////////////////////////
			PriorityArray(const PriorityArray<T> & rhs);




			////////////////////////////////////////////////////////////////////////////////////////////////////
			/// \fn	void operator= (const PriorityArray<T> & rhs)
			///
			/// \brief	Copy operator. 
			///
			/// \author	khaos
			/// \date	12.12.2009
			///
			/// \param	[in]	rhs	The right hand side object. 
			////////////////////////////////////////////////////////////////////////////////////////////////////
			void operator = (const PriorityArray<T> & rhs);

			////////////////////////////////////////////////////////////////////////////////////////////////////
			/// \fn	const T & operator[] (tIndex index) const
			///
			/// \brief	Casting operator. 
			///
			/// \author	khaos
			/// \date	12.12.2009
			///
			/// \param	[in]	index	The position of the element we want.
			///
			/// \return	Returns the element at the specified index.
			////////////////////////////////////////////////////////////////////////////////////////////////////
			const T & operator [] (tIndex index) const;

			////////////////////////////////////////////////////////////////////////////////////////////////////
			/// \fn	T & operator[] (tIndex index)
			///
			/// \brief	Casting operator. 
			///
			/// \author	khaos
			/// \date	12.12.2009
			///
			/// \param	[in]	index	The position of the element we want.
			///
			/// \return	Returns the element at the specified index.
			////////////////////////////////////////////////////////////////////////////////////////////////////
			T & operator [] (tIndex index);




			////////////////////////////////////////////////////////////////////////////////////////////////////
			/// \fn	void Clear()
			///
			/// \brief	Clears this PriorityArray.
			///
			/// \author	Markus
			/// \date	22.01.2010
			////////////////////////////////////////////////////////////////////////////////////////////////////
			void Clear();

			////////////////////////////////////////////////////////////////////////////////////////////////////
			/// \fn	tSize Size() const
			///
			/// \brief	Returns the size of the PriorityArray.
			///
			/// \author	Markus
			/// \date	22.01.2010
			///
			/// \return	The size of the PriorityArray.
			////////////////////////////////////////////////////////////////////////////////////////////////////
			tSize Size() const;

			////////////////////////////////////////////////////////////////////////////////////////////////////
			/// \fn	T & At(tSize index)
			///
			/// \brief	Returns the element at the specified index.
			///
			/// \author	Markus
			/// \date	22.01.2010
			///
			/// \param	[in]	index	The position of the element we want.
			///
			/// \return	The element we are looking for.
			////////////////////////////////////////////////////////////////////////////////////////////////////
			T & At(tSize index);

			////////////////////////////////////////////////////////////////////////////////////////////////////
			/// \fn	bool IsEmpty() const
			///
			/// \brief	Determines if this PriorityArray is empty.
			///
			/// \author	Markus
			/// \date	22.01.2010
			///
			/// \return	True if this PriorityArray is empty, otherwise false.
			////////////////////////////////////////////////////////////////////////////////////////////////////
			bool IsEmpty()  const;




			////////////////////////////////////////////////////////////////////////////////////////////////////
			/// \fn	void Add(const T & element, float prio)
			///
			/// \brief	Adds the specified element to the PriorityArray.
			///
			/// \author	khaos
			/// \date	12.12.2009
			///
			/// \param	[in]	element	The element we want to add. 
			/// \param	[in]	prio	The priority of the element. 
			////////////////////////////////////////////////////////////////////////////////////////////////////
			void Add(const T & element, float prio);

		protected:

			////////////////////////////////////////////////////////////////////////////////////////////////////
			/// \fn	protected: void Copy(const PriorityArray<T> & rhs)
			///
			/// \brief	Copies the given PriorityArray.
			///
			/// \author	khaos
			/// \date	12.01.2010
			///
			/// \param	[in]	rhs	The PriorityArray we want to copy.
			////////////////////////////////////////////////////////////////////////////////////////////////////
			void Copy(const PriorityArray<T> & rhs);

			////////////////////////////////////////////////////////////////////////////////////////////////////
			/// \fn	void Delete()
			///
			/// \brief	Deletes the whole PriorityArray.
			///
			/// \author	Markus
			/// \date	22.01.2010
			////////////////////////////////////////////////////////////////////////////////////////////////////
			void Delete();

			////////////////////////////////////////////////////////////////////////////////////////////////////
			/// \fn	void Destroy(T * element)
			///
			/// \brief	Destroys the given element. 
			///
			/// \author	Markus
			/// \date	22.01.2010
			///
			/// \param	[in]	element	The element we want to erase.
			////////////////////////////////////////////////////////////////////////////////////////////////////
			void Destroy(T * element);



			////////////////////////////////////////////////////////////////////////////////////////////////////
			/// \struct	Node
			///
			/// \brief	A Node of the PriorityArray.
			///			The Node represents the Element itself and it's assigned priority
			///			within the array.
			///
			/// \author	khaos
			/// \date	12.12.2009
			////////////////////////////////////////////////////////////////////////////////////////////////////
			struct Node
			{
				T m_element;
				float m_priority;
			};




			tSize m_size;
			tSize m_capacity;
			tSize m_minNodeIndex;

			Node * m_nodes;

		private:

	};





	///
	template<class T>
	void PriorityArray<T>::Copy(const Helper::PriorityArray<T> & rhs)
	{
		this->m_size = rhs.m_size;

		this->m_capacity = rhs.m_capacity;

		this->m_nodes = r_narray(Node, this->m_capacity);

		for(tIndex i = 0; i < this->m_size; i++)
		{
			this->m_nodes[i] = rhs.m_nodes[i];
		}
	}


	///
	template<class T>
	void PriorityArray<T>::Delete()
	{
		this->m_size = 0;
		this->m_capacity = 0;
		this->m_minNodeIndex = 0;

		if(this->m_nodes != NULL)
			r_darray(this->m_nodes);

		this->m_nodes = 0;
	}


	///
	template<class T>
	void PriorityArray<T>::Destroy(T *element)
	{
		element->~T();
	}





	///
	template<class T>
	PriorityArray<T>::PriorityArray():
	m_size(0),
		m_capacity(16),
		m_minNodeIndex(0)
	{

	}


	///
	template<class T>
	PriorityArray<T>::PriorityArray(tSize size):
	m_size(0),
		m_capacity(size),
		m_minNodeIndex(0)
	{
		this->m_nodes = r_narray(Node, size);
	}


	///
	template<class T>
	PriorityArray<T>::PriorityArray(const Helper::PriorityArray<T> &rhs)
	{
		this->Copy(rhs);
	}





	///
	template<class T>
	void PriorityArray<T>::operator =(const Helper::PriorityArray<T> &rhs)
	{
		this->Delete();
		this->Copy(rhs);
	}


	///
	template<class T>
	const T & PriorityArray<T>::operator[](tIndex index) const
	{
		return this->m_nodes[index].m_element;
	}


	///
	template<class T>
	T & PriorityArray<T>::operator [](tIndex index)
	{
		return this->m_nodes[index].m_element;
	}





	///
	template<class T>
	void PriorityArray<T>::Clear()
	{
		for(tIndex i = 0; i < this->m_size; i++)
			this->Destroy(&(this->m_nodes[i].m_element));

		this->m_size = 0;
		this->m_minNodeIndex = 0;
	}


	///
	template<class T>
	tSize PriorityArray<T>::Size() const
	{
		return this->m_size;
	}


	///
	template<class T>
	T & PriorityArray<T>::At(tSize index)
	{
		return this->m_node[index].m_element;
	}


	///
	template<class T>
	bool PriorityArray<T>::IsEmpty() const
	{
		return (this->m_size == 0);
	}



	///
	template<class T>
	void PriorityArray<T>::Add(const T &element, float prio)
	{
		if(this->m_size < this->m_capacity)
		{
			this->m_nodes[this->m_size].m_element = element;
			this->m_nodes[this->m_size].m_priority = prio;
			this->m_size++;

			if(this->m_size == this->m_capacity)
			{
				this->m_minNodeIndex = 0;
				float minprio = this->m_nodes[0].m_priority;

				for(tIndex i = 0; i < this->m_size; i++)
				{
					if(this->m_nodes[i].m_priority < minprio)
					{
						minprio = this->m_nodes[i].m_priority;
						this->m_minNodeIndex = i;
					}
				}
			}
		}
		else
		{
			if(prio > this->m_nodes[this->m_minNodeIndex].m_priority)
			{
				this->m_nodes[this->m_minNodeIndex].m_element = element;
				this->m_nodes[this->m_minNodeIndex].m_priority = prio;

				this->m_minNodeIndex = 0;
				float minprio = this->m_nodes[0].m_priority;

				for(tIndex i = 0; i < this->m_size; i++)
				{
					if(this->m_nodes[i].m_priority < minprio)
					{
						minprio = this->m_nodes[i].m_priority;
						this->m_minNodeIndex = i;
					}
				}
			}
		}
	}

}

#endif // priorityarray_h__